[蓝桥杯]历届试题(2)

题目：空间

小蓝准备用 256MB的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？

运行限制

  • 最大运行时间：1s
  • 最大运行内存: 128M

解题

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int a = 256*8*1024*1024/32;
        System.out.println(Math.abs(a));
        scan.close();
    }
}

输出67108864

题目：TOM数

题目描述

正整数的各位数字之和被Tom称为Tom数。求输入数（<2^32）的Tom数!

输入格式

每行一个整数(<2^32).

输出格式

每行一个输出,对应该数的各位数之和.

样例输入

1
2
3
12345
56123
82

样例输出

1
2
3
15
17
10

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"方法一"
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String str = scanner.next();
			int sum = 0;
            for (int i=0;i<str.length();i++){
                sum += Integer.valueOf(str.charAt(i)-'0'); //每位字符减去0的ASCII码后转为整形
            } 
			System.out.println(sum);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
"方法二"
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			String str = scanner.next();
			int sum = 0;
            for (int i=0;i<str.length();i++){
                sum += Character.getNumericValue(str.charAt(i)); //使用Character类的转换为整形方法
            } 
			System.out.println(sum);
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
"方法三"
import java.util.Scanner;

public class Seq1118 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String num = sc.next();
            char[] t = num.toCharArray();    // 使用toCharArray()方法将数字拆分字符数组
            int sum = 0;
            for(int i = 0; i<t.length; i++){
                sum += Integer.parseInt(t[i]+""); //加上""使其变为字符串，才能使用Integer类处理   
                // 注意：char类型数据会自动转化为int类型的数据，但是转换的不是数字本身
            }
            System.out.println(sum);
        }
    }
}

题目：卡片(填空题)

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝有很多数字卡片，每张卡片上都是数字 0 到 9。 小蓝准备用这些卡片来拼一些数，他想从 1 开始拼出正整数，每拼一个， 就保存起来，卡片就不能用来拼其它数了。 小蓝想知道自己能从 1 拼到多少。 例如，当小蓝有 30 张卡片，其中 0 到 9 各 3 张，则小蓝可以拼出 1 到 10， 但是拼 11 时卡片 1 已经只有一张了，不够拼出 11。 现在小蓝手里有 0 到 9 的卡片各 2021 张，共 20210 张，请问小蓝可以从 1 拼到多少？ 提示：建议使用计算机编程解决问题

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
      int count = 0;
      for(int i=0;i<20210;i++){
        String str = String.valueOf(i);
          for(int j=0;j<str.length();j++){
            if(str.charAt(j)=='1'){ //判断1用完的情况即可，因为在这里1是消耗得最快得数字
              count ++;
                /*遇到类似问题得时候可以写程序验证下，或者检查下哪个数字消耗最快，就用那个数字判断*/
            }
          }
            if(count == 2021){ //if count判断放在这比放在for j循环体里快70ms
              System.out.println(i);
              break;
            }          
      }
    }
}

题目：数字三角形

题目描述

1
2
3
4
5
    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5

上面给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

路径上的每一步只能从一个数走到下一层和它最近的左边的那个数或者右 边的那个数。此外，向左下走的次数与向右下走的次数相差不能超过 1。

输入描述

输入的第一行包含一个整数 N\ (1 \leq N \leq 100)N (1≤N≤100)，表示三角形的行数。

下面的 NN 行给出数字三角形。数字三角形上的数都是 0 至 100 之间的整数。

输出描述

输出一个整数，表示答案。

样例输入

1
2
3
4
5
6
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

1
27
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();  //接三角形得行数
        int[][] arr = new int[N][N];
        int[][] dp = new int[N][N];
        for(int i=0;i<N;i++) { //for i = 0 1 2 3 4
            for(int j=0;j<=i;j++) { //for j = 0 | 0 1 | 0 1 2 | 0 1 2 3 | 0 1 2 3 4
                arr[i][j] = sc.nextInt(); //二维数组接三角形所有元素
                /*数组arr[i][j]输出结果：7 0 0 0 0 | 3 8 0 0 0 | 8 1 0 0 0 | 2 7 4 4 0 | 4 5 2 6 5*/
            }
        }
        sc.close();
        dp[0][0] = arr[0][0];//第一个元素，不需要判断
        for(int i=1;i<N;i++) {
            dp[i][0] = dp[i-1][0] + arr[i][0]; //把三角形的左侧和算出来，即把dp[i]行的第0个元素算出来
            /*数组dp[i][j]输出结果：7 0 0 0 0 | 10 0 0 0 0 | 18 0 0 0 0 | 20 0 0 0 0 | 24 0 0 0 0*/
        }

        for(int i=1;i<N;i++) {  //for i = 1 2 3 4
            for(int j=1;j<=i;j++) { //for j = 1 | 1 2 | 1 2 3 | 1 2 3 4
                dp[i][j] = arr[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]); 
                //dp[i][j]为arr[i][j]加dp的前两项中更大的那个
            }
        }
            /*数组dp[i][j]输出结果：7 0 0 0 0 |"从这里才开始遍历dp" 10 15 0 0 0 | 18 16 15 0 0 | 20 25 20 19 0 | 24 30 27 26 24*/
            /*数组arr[i][j]输出结果：7 0 0 0 0 | 3 8 0 0 0 | 8 1 0 0 0 | 2 7 4 4 0 | 4 5 2 6 5*/

        if(N%2!=0) {
            System.out.println(dp[N-1]/*最后一行*/[N/2]/*N/2等于2，即输出最后一行第三个数据 27*/);
		   //因为奇数行的三角形，根据题目的要求向左下走的次数与向右下走的次数相差不能超过1的话，那么总是会是奇数行最后一行的中间
        }else {
            System.out.println(Math.max(dp[N-1][N/2], dp[N-1][N/2-1]));
        }
    }
}

题目：求和

问题描述

给定 nn 个整数 a_1, a_2, · · · , a_na1,a2,⋅⋅⋅,a**n ，求它们两两相乘再相加的和，即：

S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n}S=a1⋅a2+a1⋅a3+⋯+a1⋅a**n+a2⋅a3+⋯+a**n−2⋅a**n−1+a**n−2⋅a**n+a**n−1⋅a**n

输入格式

输入的第一行包含一个整数 nn。

第二行包含 n 个整数 a_1,a_2,\cdots, a_na1,a2,⋯,a**n。

输出格式

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

样例输入

1
2
4
1 3 6 9

样例输出

1
117

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;
import java.math.BigInteger;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int size = sc.nextInt();
    int[] date = new int[size];
    int sum = 0;
    for(int i=0;i<size;i++){
      date[i] = sc.nextInt();
      sum += date[i];
    }
    int res = 0;
    for(int i=0;i<size;i++){
      int temp = date[i] * (sum - date[i]); 
        //date元素里每个数字乘以了除自己以外每个数字，故比结果要求大了一倍
      res += temp;
    }
    System.out.println(res/2); //所以在这里除以二
    sc.close();
  }
}

题目：排序

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。

在冒泡排序中，每次只能交换相邻的两个元素。

小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。

例如，对于字符串 lan 排序，只需要 1 次交换。对于字符串 qiao 排序，总共需要 4 次交换。

小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要 100 次交 换，可是他忘了吧这个字符串记下来，现在找不到了。

请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要 100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {
    public static void main(String[] args) {      
        //思路1:要求字典序最小，那肯定要尽量让字母从a开始挨个出现 —— a,b,c,d.....
        //思路2:冒泡排序中，如果一个数组是完全倒序，则需要的交换的次数最多,尽可能选用完全倒序的数组，可以使字母数尽可能少
        //思路3:完全倒序的数组，用冒泡排序一共要交换 n*(n-1)/2 次 —— (n-1) + (n-2) + ... + 3 + 2 + 1 , 等差数列求和公式
        //思路4:解方程 n*(n-1)/2 = 100, 得 n ~ 14.65 ,所以字母最少为15个
        //思路5: 15个字母从 a 开开始，依次是 a,b,c,d,e,f,g,h,i,j,k,l,m,n,o
        //思路5:但是当 n = 15时，完全倒序的数组需要排105次，显然不符合题目100次的要求，所以要在基础上进行修改
        //思路6: 15个字母完全倒序 —— o,n,m,l,k,j,i,h,g,f,e,d,c,b,a 扣除5次排序，还要字典序最小，将第六个字母 j 移至第一位即可
        //最终结果:j,o,n,m,l,k,i,h,g,f,e,d,c,b,a
         //j移到前面是为了让onmlk各排序少一次，共抹去5次排序共计100了，而它自己为最小字母就不用冒泡了  
        
        System.out.println("jonmlkihgfedcba");
    }
}

题目：空间

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？

解题

1
2
3
4
5
public class Main {
    public static void main(String[] args) {
        System.out.println(Math.abs(256*1024*1024*8/32)); //Math.abs() 绝对值 absolute
    }
}

题目：跑步锻炼

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

小蓝每天都锻炼身体。

正常情况下，小蓝每天跑 1 千米。如果某天是周一或者月初（1 日），为了激励自己，小蓝要跑 2 千米。如果同时是周一或月初，小蓝也是跑 2 千米。

小蓝跑步已经坚持了很长时间，从 2000 年 1 月 1 日周六（含）到 2020 年 10 月 1 日周四（含）。请问这段时间小蓝总共跑步多少千米？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class Main {
    public static void main(String[] args) {
      //创建月份的索引，其中month[0]是填充的，为了对齐month[1] = 1月
        int month[] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; 
        int year = 2000;
        int mon = 1;
        int day = 1;
        int weekend = 6;
        int km = 0;

        while(true) {
          if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) { //判断是不是闰年
            month[2] = 29;
          } else {
            month[2] = 28;
          }

          if(day == 1 || weekend == 1 ){
            km += 2;
          } else {
            km += 1;
          }
          
          //跑完后加一天
          day++;
          weekend++;

          if(day > month[mon]){ //凑够一个月，重置day，月加
            day = 1;
            mon ++;
            if(mon>12){ //凑够一年，重置mon，年加
              year ++;
              mon = 1;
            }
          }

          if(weekend > 7){
            weekend %= 7;
          }

          if(year == 2020 && mon == 10 && day == 1){
            km += 2; //最后一天也要加上
            break;
          }
        }
      System.out.println(km);
    }
}

题目：等差素数列

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

2,3,5,7,11,13,…. 是素数序列。 类似：7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。

上边的数列公差为 30，长度为 6。

2004 年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！

有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：

长度为 10 的等差素数列，其公差最小值是多少？

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class Main {
    public static void main(String[] args) {
      int count = 0;
      for(int i=1;i<2000;i++){ //从1-1999中找素数
        if(isprime(i)){ //如果是素数
          count++; //计数加1，因为i是公差第一项
          int a = i; //把素数赋值给a
          for(int j=1;j<1000;j++){ //从1-999中找公差
            while(isprime((a+j))){ //如果素数a+公差j也是素数
              a = (a+j); //a=a加上j，若还是素数，继续循环
              count++; //计数
              if(count == 10){ //等差数列长度达到10
                System.out.println(j); //输出公差
                break;
              }
            }
            a = i;//进入下一次j循环，a重置为i，判断下个j+i是不是素数
            count = 1; //count重置为1，计公差第一项
          }
        }
      }
    }
public static boolean isprime(int num){ //时间复杂度更低
	for(int i = num-1;i>1;i--){
        if(num%i == 0) return false;
      }
      return true;
    }
}
/*public static boolean isprime(int num){//与上面效果一样
    for(int i = 2;i<num;i++){
        if(num%i==0) return false;
     }
     return true;
  }*/
    
/*    public static boolean isprime(int num){
      boolean bl = true;
      if(num < 2){
        bl = false;
      }
      for(int i=1;i<=num;i++){
        if(num % i == 0){
          if(num == i){
            bl = true;
          } else if(i != 1){
            return false;
          }
        }
      }
      return bl;
    }
*/

题目：组队

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员，组成球队的首发阵容。

每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少？

图片描述

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
//暴力搜索
public class Main {
    public static void main(String[] args) {
      int max = 0;
      int[] one = {97, 92, 0, 0, 89, 82, 0, 0, 0, 95, 0, 0, 94, 0, 0, 0, 98, 93, 0, 0};
      int[] two = {90, 85, 0, 0, 83, 86, 0, 97, 0, 99, 0, 0, 91, 83, 0, 0, 83, 87, 0, 99};
      int[] three = {0, 96, 0, 0, 97, 0, 0, 96, 89, 0, 96, 0, 0, 87, 98, 0, 99, 92, 0, 96};
      int[] four = {0, 0, 0, 80, 0, 0, 87, 0, 0, 0, 97, 93, 0, 0, 97, 93, 98, 96, 89, 95};
      int[] five = {0, 0, 93, 86, 0, 0, 90, 0, 0, 0, 0, 98, 0, 0, 98, 86, 81, 98, 92, 81};  
      for(int  a=0;a<20;a++){
        for(int b=0;b<20;b++){
          for(int c=0;c<20;c++){
            for(int d=0;d<20;d++){
              for(int e=0;e<20;e++){
                if((a!=b) && (a!=c) && (a!=d) && (a!=e) && (b!=c) && (b!=d) && (b!=e) && (c!=d) && (c!=e) && (d!=e)){
                  if(one[a]+two[b]+three[c]+four[d]+five[e]>max){
                    max = one[a]+two[b]+three[c]+four[d]+five[e];
                  }
                }
              }
            }        
          }        
        }        
      }
      System.out.println(max);
    }
}